package Niuke;

public class sdf {
    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    public class returnType{
        Node start;
        Node end;

        public returnType(Node s,Node e){
            this.start=start;
            this.end=end;
        }
        public returnType(){

        }
    }

    public Node treeToDoublyList(Node root) {
        if(root==null)
            return null;
        returnType data=transfer(root);
        data.start.left=data.end;
        data.end.right=data.start;
        return data.start;
    }
    public returnType transfer(Node root){
        if(root==null)
            return new returnType(null,null);
        returnType left=transfer(root.left);
        returnType right=transfer(root.right);

        if(left.end!=null)
            left.end.right=root;
        root.left=left.end;
        root.right=right.start;
        if(right.start!=null)
            right.start.left=root;

        returnType res = new returnType();
        res.start= left.start==null?root: left.start;
        res.end= right.end==null?root: right.end;;
        return res;

    }


    public static void main(String[] args) {
            Node head=new Node(4);
            head.left=new Node(2);
            head.right=new Node(5);
            head.left.left=new Node(1);
            head.left.right=new Node(3);
            new sdf().treeToDoublyList(head);
             System.out.println();
    }
}
